import java.util.*;

class Solution {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private Map<Integer, Integer> map = new HashMap<>();
    private int[] preorder;
    private int preIndex = 0;

    private TreeNode helper(int left, int right) {
        if (left == right) {
            return null;
        }
        int value = preorder[preIndex];
        TreeNode node = new TreeNode(value);
        Integer index = map.get(value);
        preIndex++;
        node.left = helper(left, index);
        node.right = helper(index + 1, right);
        return node;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        int index = 0;
        for (int item : inorder) {
            map.put(item, index++);
        }
        return helper(0, inorder.length);
    }

    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        Solution s = new Solution();
    }
}